package code.oldCode.feishuSpecializedTraining.dynamic;

/**
 * @author 26029
 * @date 2025/3/26
 * @description
 */
public class MyDP9 {
    // 300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        // 1 <= nums.length <= 2500
        int len = nums.length;
        // dp[i]表示前i个数字，以第i个数字为结尾，构成的最长递增子序列长度，动态规划O(n^2)
        int[] dp = new int[len];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            if (dp[i] > max)
                max = dp[i];
        }

        return max;
    }

    public int lengthOfLIS_greedy_binarySearch(int[] nums) {
        // 贪心+二分 O(nlog2n)
        // ※tails[k]表示长度为k+1的最长递增子序列的最小末尾元素※
        int len = nums.length;
        int[] tails = new int[len];
        int nowMaxLen = 0;
        for (int num : nums) {
            int left = 0, right = nowMaxLen - 1;
            int pos = nowMaxLen;
            while (left <= right) {
                // 二分查找找第一个≥num的位置（即插入位置）
                int mid = left + (right - left) / 2;
                if (tails[mid] >= num) {
                    pos = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            tails[pos] = num;
            if (pos == nowMaxLen)
                nowMaxLen++;
        }

        return nowMaxLen;
    }

    // 674. 最长连续递增序列
    public int findLengthOfLCIS(int[] nums) {
        // 1 <= nums.length <= 104
        int len = nums.length;
        // dp[i]表示以nums[i]为结尾的最长连续递增序列的长度
        int[] dp = new int[len];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            if (nums[i] > nums[i - 1])
                dp[i] = Math.max(dp[i], dp[i - 1] + 1);
            if (dp[i] > max)
                max = dp[i];
        }
        return max;
    }

    // 718. 最长重复子数组
    public int findLength(int[] nums1, int[] nums2) {
        // 本题还有一个哈希+二分的解法，暂且不看
        // 1 <= nums1.length, nums2.length <= 1000
        int len1 = nums1.length, len2 = nums2.length;
        // dp[i][j]表示nums1的以i结尾，nums2的以j结尾的最长公共子数组长度
        // dp[i][j] = nums1[i] == nums2[j] ? dp[i-1][j-1] + 1 : 0
        int[][] dp = new int[len1 + 1][len2 + 1];
        int max = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    // 1143. 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        // 1 <= text1.length, text2.length <= 1000
        int len1 = text1.length(), len2 = text2.length();
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[][] dp = new int[len1 + 1][len2 + 1];
        // dp[i][j]表示截止到i - 1，j - 1的最长公共子序列长度
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
}
